package cn.dlc.com.graph;

import cn.dlc.com.stack.Stack;
import lombok.Data;

/**
 * @author 邓立川
 * @date 2021/3/30 22:06
 * @desc 拓扑排序，基于DirectedCycle和DepthFirstOrder
 */
@Data
public class TopLogical {

    // :顶点的拓扑排序
    private Stack<Integer> order;

    public TopLogical(Digraph G){
        // 调用检测环
        DirectedCycle directedCycle = new DirectedCycle(G);
        // 调用序列化
        if(!directedCycle.hasCycle()) {
            DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
            // 直接获取拓扑排序
            order = depthFirstOrder.getReversePost();
        }
    }

    // 判断图G是否有环
    public boolean isCycle(){
        // 为空表示有环
        return order == null;
    }

    // 获取拓扑排序的所有顶点
    public Stack<Integer> order() {
        return this.getOrder();
    }
}
